#include <iostream>
#include <vector>
#include <sstream>
#include "core/SeqList.h"
#include "core/LinkedList.h"
#include "core/DoublyLinkedList.h"
#include "core/Polynomial.h"
#include "algorithms/ReverseList.h"
#include "algorithms/RightShift.h"
#include "core/StaticList.h"
#include "algorithms/GetNeighbors.h"
#include "algorithms/Josephus.h"

using namespace std;

void displayMainMenu() {
    cout << "\n数据结构上机作业测试平台" << endl;
    cout << "1. 顺序表操作测试" << endl;
    cout << "2. 单向链表操作测试" << endl;
    cout << "3. 链表倒置算法测试" << endl;
    cout << "4. 双向链表操作测试" << endl;
    cout << "5. 多项式操作测试" << endl;
    cout << "6. 顺序表右移算法测试" << endl;
    cout << "7. 静态链表操作测试" << endl;
    cout << "8. 静态链表右移算法测试" << endl;
    cout << "9. 双向链表相邻节点查找测试" << endl;
    cout << "10. 约瑟夫环问题测试" << endl;
    cout << "0. 退出程序" << endl;
    cout << "请选择测试项目: ";
}

vector<int> getInputArray() {
    vector<int> arr;
    string input;
    
    cout << "请输入元素序列（用空格分隔，如：1 2 3 4 5）: ";
    cin.ignore();
    getline(cin, input);
    
    stringstream ss(input);
    int num;
    while (ss >> num) {
        arr.push_back(num);
    }
    
    return arr;
}

void testSeqList() {
    cout << "\n顺序表操作测试" << endl;
    Seqlist<int> list;
    int choice, position, value;
    
    vector<int> initialData = getInputArray();
    for (size_t i = 0; i < initialData.size(); i++) {
        list.insert(i + 1, initialData[i]);
    }
    
    do {
        cout << "\n当前顺序表: ";
        list.display();
        cout << "\n顺序表操作菜单:" << endl;
        cout << "1. 插入元素" << endl;
        cout << "2. 删除元素" << endl;
        cout << "3. 查找元素（按值）" << endl;
        cout << "4. 查找元素（按位置）" << endl;
        cout << "5. 计算平均值并插入中间" << endl;
        cout << "6. 显示顺序表" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1:
                cout << "输入插入位置: ";
                cin >> position;
                cout << "输入插入值: ";
                cin >> value;
                if (list.insert(position, value)) {
                    cout << "插入成功!" << endl;
                }
                break;
            case 2:
                cout << "输入删除位置: ";
                cin >> position;
                if (list.remove(position, value)) {
                    cout << "删除的元素: " << value << endl;
                }
                break;
            case 3:
                cout << "输入要查找的值: ";
                cin >> value;
                position = list.find(value);
                if (position > 0) {
                    cout << "元素 " << value << " 在位置: " << position << endl;
                } else {
                    cout << "未找到元素 " << value << endl;
                }
                break;
            case 4:
                cout << "输入要查找的位置: ";
                cin >> position;
                if (list.getElement(position, value)) {
                    cout << "位置 " << position << " 的元素是: " << value << endl;
                }
                break;
            case 5:
                list.calculateInsert();
                break;
            case 6:
                list.display();
                break;
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
    } while(choice != 0);
}

void testLinkedList() {
    cout << "\n单向链表操作测试" << endl;
    LinkedList list;
    int choice, position, value;
    
    vector<int> initialData = getInputArray();
    int* arr = new int[initialData.size()];
    for (size_t i = 0; i < initialData.size(); i++) {
        arr[i] = initialData[i];
    }
    
    cout << "选择创建方式: 1-头插法 2-尾插法: ";
    cin >> choice;
    if (choice == 1) {
        list.createHeadInsert(arr, initialData.size());
    } else {
        list.createTailInsert(arr, initialData.size());
    }
    delete[] arr;
    
    do {
        cout << "\n当前链表: ";
        list.display();
        cout << "\n链表操作菜单:" << endl;
        cout << "1. 插入元素" << endl;
        cout << "2. 按值删除元素" << endl;
        cout << "3. 按位置删除元素" << endl;
        cout << "4. 按值查找元素" << endl;
        cout << "5. 按位置查找元素" << endl;
        cout << "6. 显示链表" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1:
                cout << "输入插入位置: ";
                cin >> position;
                cout << "输入插入值: ";
                cin >> value;
                list.insert(position, value);
                break;
            case 2:
                cout << "输入要删除的值: ";
                cin >> value;
                list.removeByValue(value);
                break;
            case 3:
                cout << "输入要删除的位置: ";
                cin >> position;
                list.removeByPosition(position);
                break;
            case 4:
                cout << "输入要查找的值: ";
                cin >> value;
                list.findPositionByValue(value);
                break;
            case 5:
                cout << "输入要查找的位置: ";
                cin >> position;
                list.findValueByPosition(position);
                break;
            case 6:
                list.display();
                break;
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
    } while(choice != 0);
}

void testReverseList() {
    cout << "\n链表倒置算法测试" << endl;
    
    vector<int> data = getInputArray();
    if (data.empty()) {
        cout << "输入为空!" << endl;
        return;
    }
    
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for (int val : data) {
        ListNode* newNode = new ListNode(val);
        if (!head) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    
    cout << "原始链表: ";
    ListNode* current = head;
    while (current) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
    
    ListNode* reversedHead = reverseList(head);
    
    cout << "倒置后链表: ";
    current = reversedHead;
    while (current) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
    
    current = reversedHead;
    while (current) {
        ListNode* temp = current;
        current = current->next;
        delete temp;
    }
    
    cout << "按回车键继续...";
    cin.ignore();
    cin.get();
}

void testDoublyLinkedList() {
    cout << "\n双向链表操作测试" << endl;
    DoublyLinkedList dll;
    int choice, value, target, position;
    
    vector<int> initialData = getInputArray();
    for (int val : initialData) {
        dll.insertAtTail(val);
    }
    
    do {
        cout << "\n当前链表(正向): ";
        dll.printListForward();
        cout << "当前链表(反向): ";
        dll.printListBackward();
        
        cout << "\n双向链表操作菜单:" << endl;
        cout << "1. 头部插入" << endl;
        cout << "2. 尾部插入" << endl;
        cout << "3. 在指定值后插入" << endl;
        cout << "4. 在指定值前插入" << endl;
        cout << "5. 在指定位置插入" << endl;
        cout << "6. 删除指定值" << endl;
        cout << "7. 正向显示" << endl;
        cout << "8. 反向显示" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1:
                cout << "输入要插入的值: ";
                cin >> value;
                dll.insertAtHead(value);
                break;
            case 2:
                cout << "输入要插入的值: ";
                cin >> value;
                dll.insertAtTail(value);
                break;
            case 3:
                cout << "输入目标值: ";
                cin >> target;
                cout << "输入要插入的值: ";
                cin >> value;
                dll.insertAfter(target, value);
                break;
            case 4:
                cout << "输入目标值: ";
                cin >> target;
                cout << "输入要插入的值: ";
                cin >> value;
                dll.insertBefore(target, value);
                break;
            case 5:
                cout << "输入插入位置: ";
                cin >> position;
                cout << "输入要插入的值: ";
                cin >> value;
                dll.insertAtPosition(position, value);
                break;
            case 6:
                cout << "输入要删除的值: ";
                cin >> value;
                dll.deleteNode(value);
                break;
            case 7:
                dll.printListForward();
                break;
            case 8:
                dll.printListBackward();
                break;
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
    } while(choice != 0);
}
    
void testPolynomial() {
    cout << "\n=== 多项式操作测试 ===" << endl;
    
    PolynomialCalculator poly;
    int choice, coef, exp;
    
    do {
        cout << "\n当前多项式: ";
        poly.display();
        
        cout << "\n多项式操作菜单:" << endl;
        cout << "1. 添加项" << endl;
        cout << "2. 显示多项式" << endl;
        cout << "3. 清空多项式" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1:
                cout << "输入系数: ";
                cin >> coef;
                cout << "输入指数: ";
                cin >> exp;
                poly.addTerm(coef, exp);
                cout << "添加项: " << coef << "x^" << exp << endl;
                break;
            case 2:
                poly.display();
                break;
            case 3:
                poly.clear();
                cout << "多项式已清空" << endl;
                break;
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
    } while(choice != 0);
}

void testRightShiftAlgorithm() {
    cout << "\n=== 顺序表右移算法测试 ===" << endl;
    
    int choice;
    
    do {
        cout << "\n右移算法测试菜单:" << endl;
        cout << "1. 使用预设测试用例" << endl;
        cout << "2. 自定义输入测试" << endl;
        cout << "3. 算法原理说明" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1: {
                cout << "\n--- 预设测试用例 ---" << endl;
                
                cout << "\n测试用例1: 基本右移" << endl;
                int arr1[] = {1, 2, 3, 4, 5};
                int length1 = sizeof(arr1) / sizeof(arr1[0]);
                cout << "原始数组: ";
                displayArray(arr1, length1);
                rightShiftSequence(arr1, length1, 3);
                cout << "右移3位后: ";
                displayArray(arr1, length1);
                
                cout << "\n测试用例2: 移动位数大于长度" << endl;
                int arr2[] = {1, 2, 3, 4, 5};
                int length2 = sizeof(arr2) / sizeof(arr2[0]);
                cout << "原始数组: ";
                displayArray(arr2, length2);
                rightShiftSequence(arr2, length2, 8);
                cout << "右移8位后: ";
                displayArray(arr2, length2);
                
                cout << "\n测试用例3: 空数组" << endl;
                int arr3[] = {};
                int length3 = 0;
                cout << "原始数组: 空数组" << endl;
                rightShiftSequence(arr3, length3, 3);
                cout << "右移3位后: 空数组" << endl;
                
                cout << "\n测试用例4: 单个元素" << endl;
                int arr4[] = {42};
                int length4 = 1;
                cout << "原始数组: ";
                displayArray(arr4, length4);
                rightShiftSequence(arr4, length4, 3);
                cout << "右移3位后: ";
                displayArray(arr4, length4);
                
                cout << "\n测试用例5: 移动0位" << endl;
                int arr5[] = {1, 2, 3};
                int length5 = sizeof(arr5) / sizeof(arr5[0]);
                cout << "原始数组: ";
                displayArray(arr5, length5);
                rightShiftSequence(arr5, length5, 0);
                cout << "右移0位后: ";
                displayArray(arr5, length5);
                
                break;
            }
            case 2: {
                cout << "\n--- 自定义输入测试 ---" << endl;
                vector<int> customData = getInputArray();
                
                if (customData.empty()) {
                    cout << "输入为空！" << endl;
                    break;
                }
                
                int* arr = new int[customData.size()];
                for (size_t i = 0; i < customData.size(); i++) {
                    arr[i] = customData[i];
                }
                
                cout << "原始数组: ";
                displayArray(arr, customData.size());
                
                int shift;
                cout << "输入右移位数: ";
                cin >> shift;
                
                rightShiftSequence(arr, customData.size(), shift);
                
                cout << "右移" << shift << "位后: ";
                displayArray(arr, customData.size());
                
                delete[] arr;
                break;
            }
            case 3: {
                cout << "\n--- 三次反转法原理说明 ---" << endl;
                cout << "算法步骤:" << endl;
                cout << "1. 反转整个数组" << endl;
                cout << "2. 反转前n个元素" << endl;
                cout << "3. 反转剩余元素" << endl;
                cout << "\n示例: 数组[1,2,3,4,5]右移2位" << endl;
                cout << "步骤1: 反转整个 → [5,4,3,2,1]" << endl;
                cout << "步骤2: 反转前2个 → [4,5,3,2,1]" << endl;
                cout << "步骤3: 反转后3个 → [4,5,1,2,3]" << endl;
                cout << "结果: [4,5,1,2,3]" << endl;
                cout << "\n时间复杂度: O(n)" << endl;
                cout << "空间复杂度: O(1)" << endl;
                break;
            }
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
        
        if (choice != 0) {
            cout << "\n按回车键继续...";
            cin.ignore();
            cin.get();
        }
    } while(choice != 0);
}

void testStaticList() {
    cout << "\n=== 静态链表操作测试 ===" << endl;
    StaticList<int> staticList;
    int choice;
    
    vector<int> initialData = getInputArray();
    if (!initialData.empty()) {
        int* arr = new int[initialData.size()];
        for (size_t i = 0; i < initialData.size(); i++) {
            arr[i] = initialData[i];
        }
        staticList.createList(arr, initialData.size());
        delete[] arr;
    }
    
    do {
        cout << "\n当前静态链表: " << endl;
        staticList.display();
        cout << "\n静态链表操作菜单:" << endl;
        cout << "1. 创建新链表" << endl;
        cout << "2. 右移n位" << endl;
        cout << "3. 显示链表" << endl;
        cout << "4. 清空链表" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1: {
                vector<int> newData = getInputArray();
                if (!newData.empty()) {
                    int* arr = new int[newData.size()];
                    for (size_t i = 0; i < newData.size(); i++) {
                        arr[i] = newData[i];
                    }
                    staticList.createList(arr, newData.size());
                    delete[] arr;
                }
                break;
            }
            case 2: {
                int shift;
                cout << "输入右移位数: ";
                cin >> shift;
                staticList.rightShift(shift);
                break;
            }
            case 3:
                staticList.display();
                break;
            case 4:
                staticList.clear();
                cout << "静态链表已清空" << endl;
                break;
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
    } while(choice != 0);
}

void testStaticListRightShift() {
    cout << "\n=== 静态链表右移算法测试 ===" << endl;
    
    int choice;
    
    do {
        cout << "\n静态链表右移测试菜单:" << endl;
        cout << "1. 使用预设测试用例" << endl;
        cout << "2. 自定义输入测试" << endl;
        cout << "3. 与顺序表右移对比" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1: {
                cout << "\n--- 静态链表预设测试用例 ---" << endl;
                
                cout << "\n测试用例1: 基本右移" << endl;
                int arr1[] = {1, 2, 3, 4, 5};
                StaticList<int> list1;
                list1.createList(arr1, 5);
                cout << "原始链表: ";
                list1.display();
                list1.rightShift(3);
                cout << "右移3位后: ";
                list1.display();
                
                cout << "\n测试用例2: 移动位数大于长度" << endl;
                int arr2[] = {1, 2, 3, 4, 5};
                StaticList<int> list2;
                list2.createList(arr2, 5);
                cout << "原始链表: ";
                list2.display();
                list2.rightShift(8);
                cout << "右移8位后: ";
                list2.display();
                
                cout << "\n测试用例3: 单个元素" << endl;
                int arr3[] = {42};
                StaticList<int> list3;
                list3.createList(arr3, 1);
                cout << "原始链表: ";
                list3.display();
                list3.rightShift(3);
                cout << "右移3位后: ";
                list3.display();
                
                break;
            }
            case 2: {
                cout << "\n--- 自定义输入测试 ---" << endl;
                vector<int> customData = getInputArray();
                
                if (customData.empty()) {
                    cout << "输入为空！" << endl;
                    break;
                }
                
                int* arr = new int[customData.size()];
                for (size_t i = 0; i < customData.size(); i++) {
                    arr[i] = customData[i];
                }
                
                StaticList<int> customList;
                customList.createList(arr, customData.size());
                delete[] arr;
                
                cout << "原始链表: ";
                customList.display();
                
                int shift;
                cout << "输入右移位数: ";
                cin >> shift;
                
                customList.rightShift(shift);
                
                cout << "右移" << shift << "位后: ";
                customList.display();
                break;
            }
            case 3: {
                cout << "\n--- 静态链表 vs 顺序表右移对比 ---" << endl;
                int testArr[] = {1, 2, 3, 4, 5};
                int length = 5;
                int shift = 2;
                
                cout << "测试数据: ";
                displayArray(testArr, length);
                cout << "右移位数: " << shift << endl;
                
                int seqArr[5];
                for (int i = 0; i < length; i++) seqArr[i] = testArr[i];
                rightShiftSequence(seqArr, length, shift);
                cout << "顺序表结果: ";
                displayArray(seqArr, length);
                
                StaticList<int> staticList;
                staticList.createList(testArr, length);
                staticList.rightShift(shift);
                cout << "静态链表结果: ";
                staticList.display();
                
                int staticResult[5];
                staticList.toArray(staticResult);
                bool match = true;
                for (int i = 0; i < length; i++) {
                    if (seqArr[i] != staticResult[i]) {
                        match = false;
                        break;
                    }
                }
                cout << "结果一致性: " << (match ? "✓ 一致" : "✗ 不一致") << endl;
                break;
            }
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
        
        if (choice != 0) {
            cout << "\n按回车键继续...";
            cin.ignore();
            cin.get();
        }
    } while(choice != 0);
}

void testNeighborFinder() {
    cout << "\n=== 双向链表邻居查找测试 ===" << endl;
    
    DoublyLinkedList dll;
    int choice, position;
    
    cout << "请先创建双向链表：" << endl;
    vector<int> initialData = getInputArray();
    for (int val : initialData) {
        dll.insertAtTail(val);
    }
    
    do {
        cout << "\n当前链表: ";
        dll.printListForward();
        cout << "链表长度: " << dll.getLength() << endl;
        
        cout << "\n邻居查找菜单:" << endl;
        cout << "1. 查找指定位置的邻居" << endl;
        cout << "2. 重新创建链表" << endl;
        cout << "3. 显示链表" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1:
                cout << "输入要查找的位置: ";
                cin >> position;
                NeighborFinder::findNeighbors(dll, position);
                break;
            case 2:
                {
                    dll.clear();
                    cout << "重新创建链表..." << endl;
                    vector<int> newData = getInputArray();
                    for (int val : newData) {
                        dll.insertAtTail(val);
                    }
                    cout << "链表重新创建完成！" << endl;
                }
                break;
            case 3:
                cout << "正向遍历: ";
                dll.printListForward();
                cout << "反向遍历: ";
                dll.printListBackward();
                break;
            case 0:
                cout << "返回主菜单..." << endl;
                break;
            default:
                cout << "无效选择!" << endl;
        }
    } while(choice != 0);
}

void testJosephus() {
    cout << "\n=== 约瑟夫环问题求解 ===" << endl;
    
    JosephusCircle jCircle;
    int choice, n, m;
    
    do {
        cout << "\n当前环状态: ";
        jCircle.displayCircle();
        cout << "环大小: " << jCircle.getSize() << endl;
        
        cout << "\n约瑟夫环操作菜单:" << endl;
        cout << "1. 创建约瑟夫环" << endl;
        cout << "2. 求解约瑟夫问题" << endl;
        cout << "3. 显示当前环" << endl;
        cout << "4. 清空环" << endl;
        cout << "5. 经典示例测试" << endl;
        cout << "0. 返回主菜单" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        switch(choice) {
            case 1:
                cout << "输入总人数: ";
                cin >> n;
                if (n > 0) {
                    jCircle.createCircle(n);
                    cout << "创建了 " << n << " 个人的约瑟夫环" << endl;
                } else {
                    cout << "人数必须为正整数！" << endl;
                }
                break;
                
            case 2:
                if (jCircle.getSize() > 0) {
                    cout << "输入报数间隔: ";
                    cin >> m;
                    jCircle.solveJosephus(m);
                } else {
                    cout << "请先创建约瑟夫环！" << endl;
                }
                break;
                
            case 3:
                jCircle.displayCircle();
                break;
                
            case 4:
                jCircle.clear();
                cout << "环已清空" << endl;
                break;
                
            case 5:
                {
                    cout << "\n--- 经典示例测试 ---" << endl;
                    cout << "示例1: 7个人，报数到3出列" << endl;
                    JosephusCircle example1;
                    example1.createCircle(7);
                    example1.solveJosephus(3);
                    
                    cout << "\n示例2: 5个人，报数到2出列" << endl;
                    JosephusCircle example2;
                    example2.createCircle(5);
                    example2.solveJosephus(2);
                    
                    cout << "\n示例3: 10个人，报数到4出列" << endl;
                    JosephusCircle example3;
                    example3.createCircle(10);
                    example3.solveJosephus(4);
                }
                break;
                
            case 0:
                cout << "返回主菜单..." << endl;
                break;
                
            default:
                cout << "无效选择!" << endl;
        }
    } while(choice != 0);
}

int main() {
    int mainChoice;
    
    setlocale(LC_ALL, "zh_CN.UTF-8");
    
    do {
        displayMainMenu();
        cin >> mainChoice;
        
        switch(mainChoice) {
            case 1:
                testSeqList();
                break;
            case 2:
                testLinkedList();
                break;
            case 3:
                testReverseList();
                break;
            case 4:
                testDoublyLinkedList();
                break;
            case 5:
                testPolynomial();
                break;
            case 6:
                testRightShiftAlgorithm();
                break;
            case 7:
                testStaticList();
                break;
            case 8:
                testStaticListRightShift();
                break;
            case 9:
                testNeighborFinder();
                break;
            case 10:
                testJosephus();
                break;
            case 0:
                cout << "第二章上机作业结束" << endl;
                break;
            default:
                cout << "无效选择，请重新输入！" << endl;
        }
    } while(mainChoice != 0);
    
    return 0;
}
